package likou;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

/**
 * @author: 唐小尊
 * @email: 1171702529@qq.com
 * @cate: 2021/06/06 23:52
 */
public class _15 {
    public static void main(String[] args) {
        System.out.println(threeSum(new int[]{-1,0,1,2,-1,-4}));
    }

    public static List<List<Integer>> threeSum(int[] nums) {
        List<List<Integer>> res = new ArrayList<>();
        Arrays.sort(nums);
        int one ,two,three;
        for(int i=0;i<nums.length-2;){
            while(i<nums.length-2&&i>0&&nums[i]==nums[i-1]){
                i++;
            }
            if(i<nums.length-2){
                one = nums[i];
                int temp = -one;
                for(int j=i+1;j<nums.length-1;){
                    while(j<nums.length-1&&j>i+1&&nums[j]==nums[j-1]){
                        j++;
                    }
                    if(j<nums.length-1){
                        two = nums[j];
                        for(int k=j+1;k<nums.length;k++){
                            while(k<nums.length&&k>j+1&&nums[k]==nums[k-1]){
                                k++;
                            }
                            if(k<nums.length){
                                three = nums[k];
                                if(two+three==temp){
                                    List<Integer> list = new ArrayList<>();
                                    list.add(one);
                                    list.add(two);
                                    list.add(three);
                                    res.add(list);
                                }
                            }
                        }
                    }
                    j++;
                }
            }
            i++;
        }
        return res;
    }

    /**
     * 剪枝后！
     * @param nums
     * @return
     */
    public List<List<Integer>> threeSum2(int[] nums) {
        List<List<Integer>> res = new ArrayList<>();
        Arrays.sort(nums);
        int one ,two,three;
        for(one=0;one<nums.length-2;one++){
            if(one>0&&nums[one]==nums[one-1]){
                continue;
            }
            int target = -nums[one];
            three = nums.length-1;
            for(two=one+1;two<nums.length-1;two++){
                if(two>one+1&&nums[two]==nums[two-1]){
                    continue;
                }
                // 需要保证 b 的指针在 c 的指针的左侧
                while (two < three && nums[two] + nums[three] > target) {
                    --three;
                }
                // 如果指针重合，随着 b 后续的增加
                // 就不会有满足 a+b+c=0 并且 b<c 的 c 了，可以退出循环
                if (two == three) {
                    break;
                }
                if(nums[two]+nums[three]==target){
                    List<Integer> list = new ArrayList<>();
                    list.add(nums[one]);
                    list.add(nums[two]);
                    list.add(nums[three]);
                    res.add(list);
                }
            }
        }
        return res;
    }
}
